package hyy_2022;

import commons.ListNode;

/**
 * 双指针法
 * 1、创建两个指针pA、pB, 初始化时分别指向两个链表的头节点headA 和 headB,然后两个指针依次遍历两个链表的每个节点
 * 2、每步操作需要同时更新指针pA和pB
 * 3、如果指针pA不为空,则将指针pA移到下一个节点; 如果指针pB不为空,则将指针pB移到下一个节点
 * 4、如果指针pA为空,则将指针pA移到链表headB的头节点; 如果指针pB为空,则将指针pB移到链表headA的头节点
 * 5、当pA和pB指向同一个节点或者都为null时,返回它们指向的节点或者null
 *
 * 证明：
 *  headA : a + c = m
 *  headB : b + c = n
 *  a+c+b = b+c+a
 */
public class _0714_160_Offer52_IntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
